1. Technical Field
This disclosure generally relates to branch prediction to improve processor performance, and more specifically relates to the use of branch history tables to improve processor performance.
2. Background Art
Almost all modern processors use branch prediction to improve performance of program execution. Most branch predictors use a branch history table (BHT) to track outcomes of recent branches. Typically each entry in the branch history table is a 2-bit saturating counter, with a value of 00 representing “strongly not taken”, a value of 01 representing “weakly not taken”, a value of 10 representing “weakly taken”, and a value of 11 representing “strongly taken.” The value of a BHT entry is used to predict whether or not a branch will be taken. A saturating counter means that an attempt to increment a maximum value of the counter results in the same maximum value, and an attempt to decrement a minimum value of the counter results in the same minimum value, while incrementing and decrementing between the minimum and maximum occur the same as in typical binary counters, by increasing the value of the counter by one or decreasing the value of the counter by one.
Updates to branch history table counters are typically done by saving the counter value when the counter is fetched from the branch history table, then incrementing or decrementing the saved value once execution shows whether the branch was taken or not. Temporarily saving the value, then incrementing or decrementing the value is typically done because the read port of the branch history table is so busy with fetches that is it unavailable for a subsequent read to determine the current counter value. By saving the counter value when fetched, this eliminates the need of reading the counter a second time to determine the current counter value. However, incrementing or decrementing the saved counter value instead of the current counter value can cause problems when the saved counter value is stale. This can happen, for example, when other branches update the counter value between when a branch fetches the counter and when the branch updates the counter. The result is updating the counter with a value that is other than it should be to provide accurate branch prediction.
One solution to the problem of stale data is to provide a branch history table with two read ports so the value of a BHT counter may be read before updating the counter. A read-modify-write cycle could then assure the counter data is not stale before updating. However, implementing a BHT with two read ports requires additional space and power on the processor, so this is not an ideal solution.